﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DK.Sort
{
    public class MergeSort : ISort
    {
        private int[] DeputyArray;

        public void Sort(int[] array)
        {
            DeputyArray = new int[array.Length];
            Sort(array, 0, array.Length - 1);
        }

        private void Sort(int[] array, int start, int end) 
        {
            //结束条件
            if (start >= end) 
            {
                return;
            }

            //递归前
            var mid = start + (end - start) / 2;

            //递归
            Sort(array, start, mid);
            Sort(array, mid + 1, end);

            //递归后(回调)
            Merge(array, start, mid, end);
        }

        private void Merge(int[] array, int start, int mid, int end) 
        {
            //有序数组双指针合并法
            int index = start;
            int s = start;
            int m = mid + 1;
            while (s <= mid && m <= end) 
            {
                DeputyArray[index++] = array[ array[s] < array[m] ? s++ : m++];
            }
            while (s <= mid)
            {
                DeputyArray[index++] = array[s++];
            }
            while (m <= end)
            {
                DeputyArray[index++] = array[m++];
            }
            for (int i = start; i <= end; i++)
            {
                array[i] = DeputyArray[i];
            }
        }

    }
}
